#coding:gbk

MAX_ROW_INDEX  = 8
MAX_COL_INDDEX = 8

def get_line_count(row, col):
    if row == MAX_ROW_INDEX:
        return 1

    count = 0
    count += get_line_count(row + 1, col)
    if col != 0:
        count += get_line_count(row + 1, col - 1)
    if col != MAX_COL_INDDEX:
        count += get_line_count(row + 1, col + 1)
    return count

def dump_LL(LL):
    for L in LL:
        print L

def get_line_list(row, col, L):
    LL = []

    TL = L[::]
    TL.append((row, col))

    if row == MAX_ROW_INDEX:
        LL.append(TL)
        return LL

    LL1 = []
    LL2 = []
    LL3 = []

    if col != 0:
        LL1 = get_line_list(row + 1, col - 1, TL)
    LL2 = get_line_list(row + 1, col, TL)
    if col != MAX_COL_INDDEX:
        LL3 = get_line_list(row + 1, col + 1, TL)

    return LL1 + LL2 + LL3

def main2():
    for col in range(9):
        LL = get_line_list(0, col, [])
        print '-' * 80
        dump_LL(LL)

def main():
    total_count = 0
    for col in range(9):
        count = get_line_count(0, col)
        print col, count
        total_count += count

    print total_count

if __name__ == '__main__':
    main()
    main2()

